package zhengqc.sort.merge_sort;

import zhengqc.sort.Sort;

import java.util.Arrays;

public class MergeSortBU<E extends Comparable<E>> extends Sort<E> {
    private E[] tempArray;
    public MergeSortBU() {
        this.sortName = "MergeSortBU";
        this.tempArray = null;
    }

    /* 合并两个有序的区间 array[left...mid] 和 array[mid+1...right] */
    private void merge(E[] array, int left, int mid, int right) {
        System.arraycopy(array, left, this.tempArray, left, right-left+1);
        int i = left, j = mid+1;
        // 每轮循环为 array[k] 赋值
        for (int k = left; k <= right; ++k) {
            if (i > mid) {
                array[k] = this.tempArray[j];  ++j;
            } else if (j > right) {
                array[k] = this.tempArray[i];  ++i;
            } else if (this.tempArray[i].compareTo(this.tempArray[j]) <= 0) {
                array[k] = this.tempArray[i];  ++i;
            } else {
                array[k] = this.tempArray[j];  ++j;
            }
        }
    }
    @Override
    public void sort(E[] array) {
        // 这里对归并排序过程中用到的临时数组预先分配空间
        this.tempArray = Arrays.copyOf(array, array.length);
        int n = array.length;
        // 遍历合并区间的产犊
        for (int size = 1; size < n; size += size) {
            // 合并 array[left, left+size-1] 和 array[left+size, left+2*size-1]
            for (int left = 0; left+size < n; left += (size + size)) {
                if (array[left+size-1].compareTo(array[left+size]) > 0) {
                    merge(array, left, left+size-1, Math.min(left+size+size-1, n-1));
                }
            }
        }
        this.tempArray = null;
    }
}
